package com.wuxuan.algorithm_homework.linkedList;

import java.util.ArrayList;
import java.util.List;

public class LinkedListProblems {
    class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public Node reverseList(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            // 先保存后面一个节点
            Node next = cur.next;
            // 然后让当前节点指向前一个节点
            cur.next = pre;
            // 保存当前节点为前节点
            pre = cur;
            // 然后移动到下一个节点
            cur = next;
        }
        // cur = null ,此时前节点即 反转后的头节点
        return pre;
    }

    /**
     * 定位节点
     * <p>
     * 找到固定节点，例如中间节点，倒数第n个节点；
     * <p>
     * 方法一：快慢指针
     *
     * @param head
     * @return
     */
    public Node middleNode1(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node slow = head;
        Node fast = head;
        //如果这里如下这样写，有什么问题？
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
        //比如 1 -> 2 -> 3
        //    s,f
        //再进行一个while
        //    1 -> 2 -> 3
        //         s    f
        // return 2

        //比如 1 -> 2 -> 3 -> 4
        //    s,f
        //    1 -> 2 -> 3 -> 4
        //         s    f
        //    1 -> 2 -> 3 -> 4
        //              s         f
        //return 3

        //综上，如果这样写的话，链表节点数如果为奇数，则返回的是中间节点
        //如果为偶数，则会返回中间两个节点的后一个节点

        //而如果有fast.next.next != null
        //
        //比如 1 -> 2 -> 3 -> 4
        //    s,f
        //    1 -> 2 -> 3 -> 4
        //         s    f
        //到这一步的时候就不会再进行while循环，return 2
        //也就是如果为偶数，则会返回中间两个节点的前一个节点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //思：fast.next.next!= null写了后，fast.next!= null有必要写吗？

        //fast.next != null 是必要的，以防止 NullPointerException。
        //就是说如果这个node是null的话，他就都不是一个node对象，自然也没有next
        //fast.next.next != null 也是必要的，以确保 fast 可以安全地移动两步。

        return slow;
    }

    /**
     * 定位节点
     * <p>
     * 找到固定节点，例如中间节点，倒数第n个节点；
     * <p>
     * 方法二：统计链表节点数,再数学计算出固定的位置
     *
     * @param head
     * @return
     */
    public Node middleNode2(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        int size = getLinkedListSize(head);


        int mid = size / 2;
        int step = mid - 1;

        Node cur = head;
        while (step != 0) {
            step--;
            cur = cur.next;
        }
        return cur;
    }

    private int getLinkedListSize(Node head) {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }


    /**
     * 合并两个递增的链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public Node mergeTwoLists(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        Node dummyHead = new Node(0);
        Node cur = dummyHead;
        Node cur1 = head1;
        Node cur2 = head2;

        while (cur1 != null && cur2 != null) {
            if (cur1.value <= cur2.value) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;

        }

        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }

        return dummyHead.next;
    }

    /**
     * 链表环问题
     * <p>
     * 1.检测环的存在 - 快慢指针
     * <p>
     * // 1 -> 2 -> 3 -> 4 -> 5
     *
     * @param head
     * @return
     */
    public boolean hasCycle(Node head) {
        if (head == null) {
            return false;
        }

        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        //如果走完了整个链表，并没有重合的时候，说明没有环
        return false;
    }

    /**
     * 2.环的入口
     *
     * @param head
     * @return
     */
    public Node cycleEntrance(Node head) {
        if (head == null) {
            return null;
        }

        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                // cur == slow
                //此时，cur或slow的位置即为环的入口
                return slow;
            }
        }
        return null;
    }

    /**
     * 3.环的长度
     *
     * @param head
     * @return
     */
    public int cycleLength(Node head) {
        return 0;
    }


    /**
     * 重排链表
     *
     * @param head
     */
    public void reorderList(Node head) {
        if (head == null || head.next == null) {
            return;
        }

        // 使用快慢指针找到中间节点
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时slow为中间节点
        //反转从中间节点断开后的后半部分
        Node secondHalf = reverseList(slow.next);

        //前半部分和后半部分断开
        slow.next = null;

        //合并两个链表
        Node firstHalf = head;
        Node dummyNode = new Node(0);
        Node cur = dummyNode;
        while (secondHalf != null) {
            cur.next = firstHalf;
            firstHalf = firstHalf.next;
            cur = cur.next;

            cur.next = secondHalf;
            secondHalf = secondHalf.next;
            cur = cur.next;
        }

        //如果链表长度为奇数，最后剩一个节点需要连接
        cur.next = firstHalf;

    }

    /**
     * 链表升序
     * @param head
     * @return
     */
    public Node sortLinkedList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 分离链表为单索引和双索引的两个链表，并返回两个链表的头结点，0 单索引，1 双索引
        List<Node> heads = splitLinkedList(head);

        Node head1 = heads.get(0);
        Node head2 = heads.get(1);

        //把第二个链表（递减）反转为递增
        head2 = reverseList(head2);

        //两个递增的链表合并
        Node node = mergeTwoLists(head1, head2);

        return node;
    }

    private List<Node> splitLinkedList(Node head) {
        List<Node> heads = new ArrayList<>();

        //获取两个子链表的头节点
        Node oddHead = new Node(0);
        Node evenHead = new Node(0);
        //定义两个指针分别在两个链表
        Node odd = oddHead;
        Node even = evenHead;
        Node cur = head;
        boolean isOdd = true;

        while (cur != null) {
            if (isOdd) {
                odd.next = cur;
                odd = odd.next;
            } else {
                even.next = cur;
                even = even.next;
            }
            cur = cur.next;
            isOdd = !isOdd;
        }

        //断开原链表的连接
        odd.next = null;
        even.next = null;

        heads.add(oddHead.next);
        heads.add(evenHead.next);
        return heads;
    }
}
